package com.wcj.tree;


import java.util.HashMap;
import java.util.Map;

/**
 * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历，
 * inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 */
public class 从前序与中序遍历序列构造二叉树 {



    int post_idx;
    int [] preorder;
    int [] inorder;
    Map<Integer,Integer> idx_map = new HashMap<Integer,Integer>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        // 从后序遍历最后一个元素开始
        post_idx = 0;

        // 建立键值对哈希表
        int idx = 0;
        for (int i : inorder) {
            idx_map.put(i,idx++);
        }
        return helper(0,inorder.length - 1);
    }


    private TreeNode helper(int in_left, int in_right) {
        if (in_left > in_right){
            return null;
        }
        // 找出后序遍历第一位作为树的根
        int root_val = preorder[post_idx];
        TreeNode root = new TreeNode(root_val);

        // 根据根在中序遍历中的位置，分树
        int index = idx_map.get(root_val);
        post_idx++;
        //构造左子树
        root.left = helper(in_left,index - 1);
        //构造右子树
        root.right = helper(index + 1,in_right);
        return root;
    }
}
